package club.xiaojiawei.binarytree;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/11/22 10:37 PM
 * @question 104. 二叉树的最大深度
 * @description 给定一个二叉树，找出其最大深度。
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class MaxDepth104 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        TreeNode right = new TreeNode(20);
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        root.right = right;
        int result = maxDepth2(root);
        System.out.println(result);
    }

    /**
     * 递归+DFS
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        return recursion(root);
    }

    public static int recursion(TreeNode node){
        return Math.max(node.left == null? 0 : recursion(node.left), node.right == null? 0 : recursion(node.right)) + 1;
    }

    /**
     * 民间-递归+DFS
     * @param root
     * @return
     */
    public static int maxDepth2(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth2(root.left), maxDepth2(root.right)) + 1;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
